// Z函数
// https://soj.turingedu.cn/problem/60502/

char str[maxn];
int z[maxn];

void Zcal(char *s, int len) {
    z[0] = 0;
    for (int i = 1, l = 0, r = -1; i < len; ++i) {
        int tmp = i > r ? 0 : min(z[i - l], r - i + 1);
        while (i + tmp < len && s[tmp] == s[i + tmp])
            ++tmp;
        z[i] = tmp--;
        if (i + tmp > r) l = i, r = i + tmp;
    }
}
